# Optimal Substructure

• 2026년 7월 30일 알고리즘
  동적 계획법 ③ — 구간을 어디서 자를 것인가

  행렬 M₁×…×Mₙ을 곱할 때 결과는 같아도 곱셈 횟수는 괄호를 어디에 치느냐로 달라진다. (3×2)(2×4)(4×2)는 48번 대 28번. '이 구간의 마지막 곱을 어디서 하는가'라는 결정에서 M[i,j]=minₖ(M[i,k]+M[k+1,j]+d_{i-1}d_k d_j)를 세우고, 짧은 구간부터 채워 O(n³)에 푼다. dp-2의 결정 사고를 원소에서 구간으로 확장한다.

• 2026년 7월 28일 알고리즘
  동적 계획법 ② — 점화식은 어떻게 세우는가

  날마다 일급이 다르고 연속된 날엔 일할 수 없을 때 총 일급을 최대화한다. '최적해가 마지막 날을 포함하는가?'라는 결정 하나에서 S(n)=max(S(n-1), S(n-2)+aₙ)을 유도하고, 상향식으로 O(n)에 푼다. DP①이 점화식을 계산했다면 ②는 점화식을 세운다.